
通过课程进入	题 号:	114	随机数置换(teacher_main)	语言要求：	C++
背景：
假设要生成前n个自然数的一个随机置换，如{4,3,1,5,2}和{3,1,4,2,5}就是一个合法置换；
但{5,4,1,2,1}就不是，因为1出现2次而3没有。假设我们有一个随机数生成器RandInt(i,j),它以相同概率生成i到j之间的整数，
下面是三个算法。
（1） 如下填入从A[0]到A[N-1]的数组A:为了填入A[i],生成不同于A[0],A[1],...,A[i-1]之间的随机数时，才将其填入A[i]
（2） 同算法1，但保留一个称为Used数组的附加数组，当一个随机数Ram最初被放入数组A的时候，Used[Ram]=1.这就是说，
	当用一个随机数填入A[i]时，用Used数组来测试该随机数是否已经被使用。
（3） 首先填写数组使得A[i]=i+1;然后
          For(i=1;i<N;i++)
                   Swap(&A[i],&A[RandInt(0,i)])

	要求实现以上三个算法的函数：（1对应(1)中的算法，请务必不要弄混）
	void RandomPermutation1(int n);
	void RandomPermutation2(int n);
	void RandomPermutation3(int n);
	在函数中输出为前n个自然数的一个随机置换，用,号分隔
	必须使用教师提供的随机函数，函数原型如下：
	int RandInt(int i, int j); 
	在文件中加入：extern int RandInt(int i, int j); 即可
	（在测试的时候可以使用random函数，但是在向系统提交时必须改成调用RandInt产生随机数）
	
	注意：
              1、逗号为英文输入法中逗号；
              2、输入n不为正整数时，输出error 
              3、在输出的结果后多输出",0"(不含外侧引号)表示输出结束，除此之外，其余任意多余输出视为错误。
	例如：
	1.当参数n = 5时，
	输出格式为
		1,2,3,4,5,0 
        2.例如n = 10时，数组的10个元素输出为2,8,5,1,10,9,3,6,7,4，但是需在结果后增加一个0
        因此最终输出为：
                2,8,5,1,10,9,3,6,7,4,0



#include<stdio.h>
#include<stdlib.h>
extern int RandInt(int i,int j);
void RandomPermutation1(int n)
{
	if (n<=0)
	{
		printf("error");
		return;
	}
	int *a,temp,j,i;
	a=(int *)malloc(n*sizeof(int));
	bool flag;
	for (i=0;i<n;i++)
	{
		a[i]=0;
		while (a[i]==0)
		{
			flag=false;
			temp=RandInt(1,n);
			for (j=0;j<i;j++)
				if (a[j]==temp)
					flag=true;
			if (flag==false)
				a[i]=temp;
		}		
	}
	for (i=0;i<n;i++)
		printf("%d,",a[i]);
		printf("0");
 } 
 
 void RandomPermutation2(int n)
 {
 	if (n<=0)
	{
		printf("error");
		return;
	}
 	int *a,*used,i,temp;
 		a=(int *)malloc(n*sizeof(int));
 			used=(int *)malloc(n*sizeof(int));
 	for (i=1;i<=n;i++)
 		used[i]=0;
 	for (i=0;i<n;i++)
 	{
 		a[i]=0;
 		while (a[i]==0)
 		{
 			temp=RandInt(1,n);
 			if (used[temp]==0)
 			{
 				a[i]=temp;
 				used[temp]=1;
			 }
		}
	}
	for (i=0;i<n;i++)
		printf("%d,",a[i]);
		printf("0");
 }
 void RandomPermutation3(int n)
 {
 	if (n<=0)
	{
		printf("error");
		return;
	}
 	int *a,temp,j;
 		a=(int *)malloc(n*sizeof(int));
 	for (int i=0;i<n;i++)
 		a[i]=i+1;
 	for(int i=1;i<n;i++)
    	{
    		j=RandInt(0,i);
    		temp=a[i];
    		a[i]=a[j];
    		a[j]=temp;
		}
	for (int i=0;i<n;i++)
		printf("%d,",a[i]);
		printf("0");	
 }
int main()
{
	
	return 0;
 } 